A local address network (LAN) conventionally includes at least one Ethernet data switch that provides a “bridging” function of routing data packets generated by computer systems attached to the LAN to other computer systems attached to the LAN (i.e., switching within the LAN itself). The switch has ports connected to the various computer systems of the LAN, and learns an association between its ports and the respective MAC (media access control) addresses of the computer systems, so that when a given packet arrives specifying the MAC address of one of the computer systems, the switch can use the association to direct the packet to the computer system via the corresponding port. To learn the association, the switch includes a MAC address table.
For this purpose, the switch performs the method shown in FIG. 1a. During the learning phase, when it is required to store switching data for a given 48-bit MAC address, the 48-bit MAC address 1 is input to a hash function 3, which uses it to output 5 an n-bit address. The address is input to each of m buckets 7, that is a writable segment of a memory 9 referred to as a MAC address table. Each bucket consists of a number of rows, and each row stores data in the format shown in FIG. 1b: a valid bit, control info, and a space for a 48-bit MAC address to be stored. The address generated by the hashing algorithm 3 for any given MAC address is n bits long, and selects one of the rows in each of the m buckets 7. When a MAC address is to be learned the switch checks the data stored in each of the m buckets in turn to determine if the row of the bucket corresponding to the MAC address is free (i.e., no MAC address is stored there already). If it finds one that is free, it stores there the MAC address that is being learned, and also stores there the control information the switch needs to direct data packets to having this MAC address in the header (e.g., the number of the corresponding port). The total memory used by the MAC address table 9 is thus the number m of buckets 7 times the number (2n) of rows per bucket 7 times the number of bits that are stored per bucket 7.
During a data packing switching phase, the switch determines the MAC address in the header of the data packet, again inputs this address 1 to the hash function 3 to obtain the n-bit address, and checks the m buckets 7 in turn using m comparators 11 to see whether a MAC address stored there is equal to the one in the header of the data packet. If so, the control information is output, so that the data packet can be switched using it.
It is also well known to provide a router that connects the LAN to the Internet. This router (“IP router”) has to perform IP routing, in which packets received by the router from the Internet are examined to identify whether a first section of the header of the packet (the “network identifier” portion) indicates that the packet is intended for the LAN. Only in this case, the router would examine further sections of the header of the packet (the “station identifier” portion) to identify which station on the LAN the packet was intended for. Note that within the 32-bit IP address, the network and station identifiers can be of variable lengths. Thus, the IP address 172.120.14.15 with a network identifier 172.120.14 is not the same IP address as 172.120.14.15 where the network identifier is 172.120.
The algorithm performed by the IP router is illustrated in FIG. 2a. The 32-bit IP address is broken into 32/p groups of p-bits each. Each group in turn is used to access a respective one of 32/p sections 13 of a “lookup table” 15. Each section 13, when it receives the corresponding group of bits, outputs a string 17 of w bits. The bits are passed as inputs to a respective one of a set of w AND units 19. The AND units 19 output their result to a respective flip-flop 21, which passes its output back to the corresponding AND unit 19. The outputs of the flip-flops 21 are initialized to “1” before the look-up. Thus, after all 32/p groups have been used in turn, the outputs of the flip-flops 23 will only be 1 if the output of the corresponding bit of the memory 15 was 1 for each of the groups. The outputs of the set of flip-flops 23 at this stage is a set of w bits. As explained below, one or more of these w bits may have the value 1, and of these bits the least significant is extracted by a priority encoder 25. The output of the priority encoder 25 is an address in an IP address table 27 having a depth of w. The information stored in the IP address table 27 can be used to determine the final destination of the packet. The typical structure of an item in the IP address table is shown in FIG. 2b. It contains control information and a destination port.
It is possible that there will be multiple matches (i.e., more than one of the w bits input to the priority encoder 25 will be 1). The look-up table 15 is programmed such that the addresses with the longest prefix matches are the lower significant columns of the look-up memory. Thus, in the case of multiple matches, the priority encoder 25 can choose the match with the longest prefix simply by choosing the column number on the least significant side. Thus, a router will assume an address match, even if only a few bits in the most significant portion of the 32-bit IP address match an entry in its table.
Normally, the number of IP addresses supported by an IP switch is on the order of thousands, so it may not be possible to have a single memory for the lookup-table. In this case, the lookup table may be broken down into a number of smaller memories s, each of width q, such that s×q=w.
As hardware became cheaper, smarter and faster, it has been possible to realize a significant portion of the router software routines in hardware, thus making the routers faster and more intelligent. The next logical step was to integrate IP routers and MAC-address based bridging switches to achieve higher levels of integration and thus reduce costs. These devices herein are called “layer 3 switches” to emphasize the difference between these devices and traditional layer 2 switches (in some literature, layer 3 switches are called “swooters”, i.e., switches plus routers).
Presently new applications for Ethernet are emerging, such as so-called “Ethernet in the first mile” (EFM), in which home users use Ethernet to connect to the Internet. Another new Ethernet application is digital subscriber line access multiplexers (DSLAMs), which provide functions such as permitting high-speed data transmission over existing copper telephone cables, separating voice-frequency signals from high-speed data traffic, and routing digital subscriber line (xDSL) traffic between the subscriber's end-user equipment and the network service provider's network.
To cater for all these applications, layer 3 switches have to cater for two different markets: the office market, in which the layer 3 switches need to do a lot of bridging and very little routing, and the home market, in which layer 3 switches do a lot of routing and very little, if any, bridging.